/**
 * 312. 戳气球
 * https://leetcode-cn.com/problems/burst-balloons/
 */

// /**
//  * @param {number[]} nums
//  * @param {number} begin
//  * @param {number} end
//  * @param {number[][]} dp
//  */
// function recursive(nums, begin, end, dp) {
//   if (begin >= end - 1) {
//     return 0;
//   }
//   if (dp[begin][end] >= 0) {
//     return dp[begin][end];
//   }
//   let max = 0;
//   for (let i = begin + 1; i < end; i += 1) {
//     max = Math.max(max, nums[begin] * nums[i] * nums[end] + recursive(nums, begin, i, dp) + recursive(nums, i, end, dp));
//   }
//   dp[begin][end] = max;
//   return max;
// }
//
// /**
//  * @param {number[]} nums
//  * @return {number}
//  */
// function maxCoins(nums) {
//   nums = [1, ...nums, 1];
//   const dp = new Array(nums.length);
//   for (let i = 0; i < nums.length; i += 1) {
//     dp[i] = new Array(nums.length).fill(-1);
//   }
//   return recursive(nums, 0, nums.length - 1, dp);
// }

/**
 * @param {number[]} nums
 * @return {number}
 */
function maxCoins(nums) {
  nums = [1, ...nums, 1];
  const dp = new Array(nums.length);
  for (let i = 0; i < nums.length; i += 1) {
    dp[i] = new Array(nums.length).fill(0);
  }
  for (let j = 2; j < nums.length; j += 1) {
    for (let i = j - 2; i >= 0; i -= 1) {
      let max = 0;
      for (let k = i + 1; k < j; k += 1) {
        max = Math.max(max, nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]);
      }
      dp[i][j] = max;
    }
  }
  return dp[0][nums.length - 1];
}

console.log(maxCoins([3, 1, 5, 8]) === 167);
console.log(maxCoins([1, 5]) === 10);
console.log(maxCoins([0]) === 0);
